package LintCode;

/**
 * @Classname SearchBigSortedArray
 * @Description TODO
 * @Date 2021/3/5 16:51
 * @Created by ASUS
 */
public class SearchBigSortedArray {
    static class ArrayReader {
        public int get(int i) {
            return (long) i + 1 > Integer.MAX_VALUE || (long) i - 1 < Integer.MIN_VALUE ? i : Integer.MAX_VALUE;
        }
    }

    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     * 在一个很大的有序非负整数数组中寻找特定的数，采用的是倍增的方式寻找
     *
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        // the array is already sorted, so if the first item > target
        // --> this is no item that matches the target.
        if (target < reader.get(0)) return -1;
        if (target == reader.get(0)) return 0;
        int index = 0, jump = 1;
        while (jump != 0) {
            // this while loop is order to make sure the
            // target is bigger than the value in the index + jump.
            while (jump != 0 && target <= reader.get(index + jump)) jump >>= 1;
            index += jump;
            jump <<= 1;
        }
        return reader.get(index++) == target ? index : -1;
    }
}
